package dp;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 使用最小花费爬楼梯746.java
 * @Description https://leetcode-cn.com/problems/min-cost-climbing-stairs/
 * @createTime 2021年11月30日 20:48:00
 *
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 *
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 *
 * 请你计算并返回达到楼梯顶部的最低花费
 *
 */
public class 使用最小花费爬楼梯746 {
	public int minCostClimbingStairs(int[] cost) {
		int length = cost.length;

		/**
		 * dp[i]表示 到第i个台阶需要花费的最少的体力
		 */
		int[] dp = new int[length+1];

		/**
		 * 初始化转态
		 *
		 */
		dp[0] = 0;
		dp[1] = 0;

		/**
		 * 转态方程
		 * 	dp[i]=Min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
		 */
		for (int i = 2; i <= length; i++) {
			dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
		}
		return dp[length];
	}
}
